package com.learning.lesson04dynamic;

import java.util.Arrays;

/**
 * 动态规划实践-背包问题
 *
 * @author Zongheng Ma
 * @date 2020/11/13
 */
public class KnapsackProblem {

    public static void main(String[] args) {
        // 物品重量数组
        int[] w = {1, 4, 3};
        // 物品价格数组
        int[] val = {1500, 3000, 2000};
        // 背包容量
        int m = 4;
        System.out.println(knapsackHandler(w, val, m));
    }


    /**
     * 背包问题求解
     *
     * @param w   物品重量数组
     * @param val 物品价格数组
     * @param m   背包容量
     * @return 能容纳物品总价的最大值
     */
    public static int knapsackHandler(int[] w, int[] val, int m) {
        if (w.length != val.length) {
            throw new RuntimeException("物品的价格与重量不匹配！");
        }

        // 记录商品的存放情况
        int[][] goods = new int[w.length + 1][m + 1];

        /*
         * 价格推导数组
         * 行数为物品个数+1，列数为背包容量+1
         */
        int[][] v = new int[w.length + 1][m + 1];
        // 第一列置0，背包容量为0的情况，总价格必然为0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }
        // 第一行置0，物品数量为0的情况，总价格必然为0
        Arrays.fill(v[0], 0);

        // 迭代求总价
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[i].length; j++) {
                // 取对应质量和价格时注意下标做-1修正
                if (w[i - 1] > j) {
                    /*
                     * 当前物品质量超过背包容量
                     * 总价应为当前背包放入上一个物品时的策略
                     */
                    v[i][j] = v[i - 1][j];
                } else {
                    /*
                     * 当前物品质量小于等于当前背包容量
                     * lastPrice为当前背包放入上一个物品时的总价
                     * curPrice为当前背包放入当前物品+可能剩余空间可放入物品的总价
                     * 取二者中较大为当前单元格的策略
                     */
                    int lastPrice = v[i - 1][j];
                    int curPrice = val[i - 1] + v[i - 1][j - w[i - 1]];
                    if (lastPrice < curPrice) {
                        v[i][j] = curPrice;
                        goods[i][j] = 1;
                    } else {
                        v[i][j] = lastPrice;
                    }
                }
            }
        }

        int i = goods.length - 1;
        int j = goods[0].length - 1;
        while (i > 0 && j > 0) {
            if (goods[i][j] == 1) {
                System.out.printf("第%d个物品放入背包（质量%d, 价格%d）\n", i, w[i - 1], val[i - 1]);
                j -= w[i - 1];
            } else {
                i--;
            }
        }

        // 根据推导，最后一个元素为最大总价格
        return v[w.length][m];
    }
}
